#include <bits/stdc++.h>
using namespace std;

const int MAX = 500500; // 定义最大字符串长度
char S[MAX];            // 存储输入字符串
int L[MAX], R[MAX];     // 前缀和后缀数组，用于动态规划

// 检查字符串是否已经满足条件（从第2个字符开始与目标字符串相同）
bool isSame(int N, char *s) {
  for (int i = 2; i <= N; ++i)
    if (S[i] != s[i - 1])
      return false;
  return true;
}

int main() {
  int T; // 测试用例数量
  cin >> T;

  while (T--) {
    int N; // 字符串长度
    scanf("%d", &N);
    scanf("%s", S + 1); // 从索引1开始读取字符串

    // 如果字符串已经满足条件，直接输出0
    if (isSame(N, S)) {
      printf("0\n");
      continue;
    }

    int ans = 2 * N; // 初始化答案为最大可能值
    int lt;          // 临时变量，用于存储当前累计的操作次数

    // ========== 转换为全0字符串的方案 ==========

    // 计算前缀数组：L[i]表示将前i个字符转换为全0所需的最小操作次数
    for (int i = 1; i <= N; ++i)
      L[i] = L[i - 1] + 1 + (S[i] == '0');

    // 计算后缀数组：R[i]表示将第i个到第N个字符转换为全0所需的最小操作次数
    for (int i = N; i >= 1; --i)
      R[i] = R[i + 1] + 1 + (S[i] == '0');

    // 从左到右遍历，寻找分割点，计算将字符串转换为全0的最小操作次数
    lt = 0;
    for (int i = 1; i <= N; ++i) {
      if (S[i] == '1') {
        // 在当前位置分割，左边转换为全0，右边也转换为全0
        ans = min(ans, lt + R[i]);
        lt = L[i]; // 更新左边的累计操作次数
      }
    }

    // 从右到左遍历，寻找分割点
    lt = 0;
    for (int i = N; i >= 1; --i) {
      if (S[i] == '1') {
        // 在当前位置分割，左边转换为全0，右边也转换为全0
        ans = min(ans, lt + L[i]);
        lt = R[i]; // 更新右边的累计操作次数
      }
    }

    // ========== 转换为全1字符串的方案 ==========

    // 重新计算前缀数组：转换为全1的情况
    for (int i = 1; i <= N; ++i)
      L[i] = L[i - 1] + 1 + (S[i] == '1');

    // 重新计算后缀数组：转换为全1的情况
    for (int i = N; i >= 1; --i) {
      R[i] = R[i + 1] + 1 + (S[i] == '1');
    }

    // 从左到右遍历，寻找分割点，计算将字符串转换为全1的最小操作次数
    lt = 0;
    for (int i = 1; i <= N; ++i) {
      if (S[i] == '0') {
        // 在当前位置分割，左边转换为全1，右边也转换为全1
        ans = min(ans, lt + R[i]);
        lt = L[i]; // 更新左边的累计操作次数
      }
    }

    // 从右到左遍历，寻找分割点
    lt = 0;
    for (int i = N; i >= 1; --i) {
      if (S[i] == '0') {
        // 在当前位置分割，左边转换为全1，右边也转换为全1
        ans = min(ans, lt + L[i]);
        lt = R[i]; // 更新右边的累计操作次数
      }
    }

    // 输出最小操作次数
    printf("%d\n", ans);
  }

  return 0;
}